import State, { StateType } from "./common/state";
import NFAGraph, { NFAState } from "./nfa/NFAGraph";
import RegReader from './common/regReader'
import Constant from "./common/baseElem";
import { MatchStrategyMap } from "./nfa/strategy";
import { DFAGraph, DFAState } from './dfa/DFAGraph'
import { addAll, Queue } from "./utils";

export enum Mode {
    NFA,
    DFA
}

let maxPos = 0

export class Regex {

    private nfaGraph: NFAGraph
    
    private dfaGraph: DFAGraph
    
    private constructor(regex: string) {
        if(!regex) {
            throw(new Error('empty regex'))
        }

        
        this.nfaGraph = regex2nfa(regex)
        this.nfaGraph.end.stateType = StateType.END
        this.dfaGraph = nfa2dfa(this.nfaGraph)
    }

    public static compile(regex: string) {
        return new Regex(regex)
    }
    


    /**
     * 
     * @param {string} text matched text
     * @param {Mode} mode is nfa or dfa
     * @returns {boolean} is text match regex?
     */
    public isMatch(text: string, mode: Mode = Mode.NFA): boolean {
        // console.log('mode: ', mode)
        maxPos = 0
        let start: State,
            flag = false,
            startPos = 0
        if(mode === Mode.NFA) 
            start = this.nfaGraph.start
        else  
            start = this.dfaGraph.start

        while(!(flag = absMatch(text, startPos, start))  && startPos < text.length) {
            startPos = maxPos + 1
            if(absMatch(text, maxPos, start)) {
                return true
            }
        }
        // console.log('ret flag')
        return flag
    }

    /**
     * used debugger
     */
    public get nfa() {
        return this.nfaGraph
    }

    public get dfa() {
        return this.dfaGraph
    }

    public get toJSON() {
        return {
            nfaGraph: this.nfaGraph,
        }
    }
}


/**
* 
* @param {string} regex
* @returns {NFAGraph} nfaGraph from regex string
*/
function regex2nfa(regex: string): NFAGraph {
    let reader = new RegReader(regex),
        nfaGraph: NFAGraph = null

    while(reader.hasNext) {
        let str = reader.next
        let edge: string = null
        switch(str) {
            case '(': {
                let subRegex = RegReader.getSubRegex(reader),
                    newNFAGraph = regex2nfa(subRegex)
                
                checkRepeat(reader, newNFAGraph)
                if(nfaGraph) {
                    nfaGraph.addSeriesGraph(newNFAGraph)
                }
                else {
                    nfaGraph = newNFAGraph
                }

                break
            }
            
            case '|': {
                let parallelRegex = RegReader.getParallelRegex(reader),
                    newNFAGraph = regex2nfa(parallelRegex)

                if(nfaGraph) {
                    nfaGraph.addParallelGraph(newNFAGraph)
                }
                else {
                    nfaGraph = newNFAGraph
                }

                break
            }

            case '[': {
                edge = getCharSet(reader)
                break
            }

            case '.': {
                edge = '.'
                break
            }

            case '\\': {
                let nextStr = reader.next
                if(['d', 'D', 'w', 'W', 's', 'S'].includes(nextStr)) {
                    edge = `\\${nextStr}`
                }
                else {
                    edge = nextStr
                }
                break
            }
            default: {
                edge = str
                break
            }
        }

        if(edge) {
            let start = new NFAState(),
                end = new NFAState(),
                newNFAGraph = new NFAGraph(start, end)

            start.addNext(edge, end)
            checkRepeat(reader, newNFAGraph)
            if(nfaGraph) {
                nfaGraph.addSeriesGraph(newNFAGraph)
            }
            else {
                nfaGraph = newNFAGraph
            }
        }
    }

    return nfaGraph
}


function nfa2dfa(nfaGraph: NFAGraph): DFAGraph {
    let dfaGraph = new DFAGraph(),
        dfaStateVis: Set<string> = new Set(),
        firstNFAStates: Set<State> = new Set(),
        que: Queue<DFAState> = new Queue(),
        edgeVis: Set<string> = new Set(),
        nextNFAStates: Set<State> = new Set(),
        edgeToVis: Set<State> = new Set()
    
    firstNFAStates.add(nfaGraph.start)
    addAll(firstNFAStates, getEpsNext(nfaGraph.start, new Set()))
    dfaGraph.start = dfaGraph.getOrBuild(firstNFAStates)
    que.push(dfaGraph.start)

    while(!que.empty) {
        let curDFAState = que.poll()

        edgeVis.clear()
        edgeVis.add(Constant.EPSILON)
        
        for(let curNFAState of curDFAState.nfaStates) {
            for(let edge of curNFAState.next.keys()) {
                if(edgeVis.has(edge)) continue
                //找到子状态的一条边后，将此边视作改连通分量的公共边
                nextNFAStates.clear()
                edgeVis.add(edge)
                edgeToVis.clear()
                for(let nfaState of curDFAState.nfaStates) {
                    let edgeToStates = getOrDefault(nfaState.next, edge, new Set())
                    addAll(nextNFAStates, edgeToStates)
                    //找到所有公共边可达状态，接着清除空边
                    for(let edgeToState of edgeToStates) {
                        if(edgeToVis.has(edgeToState)) continue
                        addAll(nextNFAStates, getEpsNext(edgeToState, edgeToVis))
                        edgeToVis.add(edgeToState)
                    }
                }

                let nextDFAState = dfaGraph.getOrBuild(nextNFAStates)
                curDFAState.addNext(edge, nextDFAState)
                if(!dfaStateVis.has(nextDFAState.allId) && nextDFAState.allId) {
                    que.push(nextDFAState)
                    dfaStateVis.add(nextDFAState.allId)
                }
            }
        }

        dfaStateVis.add(curDFAState.allId)
    }

    return dfaGraph
}

function getEpsNext(curState: State, stateSet: Set<State>): Set<State> {
    if(!curState.next.has(Constant.EPSILON)) {
        return new Set()
    }

    let ret: Set<State> = new Set()
    for(let state of curState.next.get(Constant.EPSILON)) {
        if(stateSet.has(state))
            continue
        ret.add(state)
        addAll(ret, getEpsNext(state, stateSet))
        stateSet.add(state)
    }

    return ret
} 


/**
 * 
 * @param {RegReader} reader 
 * @param {NFAGraph} nfaGraph 
 * <br>
 * - update graph with [*?+]
 * - TODO for zero width assertion
 */
function checkRepeat(reader: RegReader, nfaGraph: NFAGraph):void {
    let nextStr = reader.peek
    switch(nextStr) {
        case '*': {
            nfaGraph.zeroMore()
            reader.next
            break
        }
        case '+': {
            nfaGraph.oneMore()
            reader.next
            break
        }
        case '?': {
            nfaGraph.zeroOne()
            reader.next
            break
        }
        default: {
            return
        }
    }
}

/**
 * 
 * @param {RegReader} reader 
 * @returns {string} char set string
 */
function getCharSet(reader: RegReader): string {
    let result = '',
        str

    while((str = reader.next) !== ']') {
        result += str
    }

    return result
}

// function getRange(reader: RegReader): number[] {
//     let 
// }

/**
 * 
 * @param {string} text 
 * @param {number} pos 
 * @param {State} curState 
 * @returns {boolean} is match?
 * --- 
 * internal global-matching funtion 
 */
function absMatch(text: string, pos: number, curState: State):boolean {
    if(pos === text.length) {
        for(let nextState of getOrDefault(curState.next, Constant.EPSILON, new Set())) {
            if(absMatch(text, pos, nextState)) {
                return true
            }
        }  

        if(curState.isEndState) {
            return true
        }

        maxPos = Math.max(pos, maxPos)
        return false
    }

    for(let entry of curState.next.entries()) {
        let edge = entry[0],
            nextStates = entry[1]

        if(Constant.EPSILON === edge) {
            for(let nextState of nextStates) {
                if(absMatch(text, pos, nextState)) {
                    return true
                }
            }
        }
        else {
            let matchStrategy = MatchStrategyMap.getStrategy(edge)
            if(!matchStrategy.isMatch(text.charAt(pos), edge)) 
                continue

            for(let nextState of nextStates) {
                if(nextState instanceof DFAState) {
                    return absMatch(text, pos + 1, nextState)
                }
                if(absMatch(text, pos + 1, nextState)) {
                    return true
                }
            }
        }
    }
    maxPos = Math.max(maxPos, pos)
    // if(curState instanceof DFAState) 
    //     maxPos -= 1
    if(curState.isEndState) 
        return true
        
    return false
}

/**
 * 
 * @param {Map} map 
 * @param {any} keys 
 * @param {any} _default 
 * @returns {any}
 * ---
 * if dist cannot find in `map` by `key`, it will return default value as `_default`
 */
function getOrDefault<T = any, N = any>(map: Map<T, N>, key: T, _default: N): N {
    if(map.has(key)) {
        return map.get(key)
    }
    else {
        return _default
    }
}